GATE IT 2006
Q2.
The data path shown in the figure computes the number of 1s in the 32-bit input word corresponding to an unsigned even integer stored in the shift register. The unsigned counter, initially zero, is incremented if the most significant bit of the shift register is 1. The microprogram for the control is shown in the table below with missing control words for microinstructions I_1, I_2, \ldots I_n. \begin{array}{|l|c|c|c|} \hline \textbf {Microinstruction} & \textbf{Reset Counter}& \textbf{Shift left} & \textbf{Load output} \\\hline \text{BEGIN} & \text{1} & \text{0} & \text{0} \\\hline \text{I1}& \text{$?$} & \text{$?$} & \text{$?$} \\\hline \text{:} & \text{:} & \text{:} & \text{:} \\\hline \text{In} & \text{$?$} & \text{$?$} & \text{$?$} \\\hline \text{END} & \text{0} & \text{0} & \text{1} \\\hline \end{array} The counter width (k), the number of missing microinstructions (n), and the control word for microinstructions I_1, I_2, \ldots I_n are, respectively,Q4.
Which one of the choices given below would be printed when the following program is executed? #include < stdio.h > int a1[] = {6, 7, 8, 18, 34, 67}; int a2[] = {23, 56, 28, 29}; int a3[] = {-12, 27, -31}; int *x[] = {a1, a2, a3}; void print(int *a[]) { printf("%d,", a[0][2]); printf("%d,", *a[2]); printf("%d,", *++a[0]); printf("%d,", *(++a)[0]); printf("%d\n", a[-1][+1]); } main() { print(x); }Q5.
Which one of the choices given below would be printed when the following program is executed ? #include < stdio.h > struct test { int i; char *c; }st[] = {5, "become", 4, "better", 6, "jungle", 8, "ancestor", 7, "brother"}; main () { struct test *p = st; p += 1; ++p -> c; printf("%s,", p++ -> c); printf("%c,", *++p -> c); printf("%d,", p[0].i); printf("%s \n", p -> c); }Q6.
Suppose that we have numbers between 1 and 100 in a binary search tree and want to search for the number 55. Which of the following sequences CANNOT be the sequence of nodes examined?Q7.
In the 4B/5B encoding scheme, every 4 bits of data are encoded in a 5-bit codeword. It is required that the codewords have at most 1 leading and at most 1 trailing zero. How many are such codewords possible?Q8.
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. If only the root node does not satisfy the heap property, the algorithm to convert the complete binary tree into a heap has the best asymptotic time complexity ofQ9.
An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element of the array is 0. The index of the parent of elementX[i], i \neq 0, is?Q10.
In a binary tree, the number of internal nodes of degree 1 is 5, and the number of internal nodes of degree 2 is 10. The number of leaf nodes in the binary tree is